package com.hdu.other.tanxin;

public class lc1326 {
    class Solution {
        public int minTaps(int n, int[] ranges) {
            int[] right = new int[n + 1];
            for (int i = 0; i < ranges.length; i++) {
                int start = Math.max(0, i - ranges[i]);
                right[start] = Math.max(right[start], i + ranges[i]);
            }
            int ans = 0;
            int next = 0;
            int cur = 0;
            for (int i = 0; i < n; i++) {
                next = Math.max(next, right[i]);
                if (i == cur)
                {
                    if (next == cur)
                    {
                        return -1;
                    }
                    ans++;
                    cur = next;
                }
            }
            return ans;
        }
    }
}
